package com.wu.leetcode.sort.shellsort;

import java.util.Arrays;

/**
 * @author lynn
 * @date 2020/7/11 - 23:30
 * 希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，
 * 每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止
 */
public class ShellSort {
    public static void main(String[] args) {
        int[] arr = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0, 11, 10, 13, 14, 12, 16};
        shellSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    // 希尔排序进行优化 -- 移位法
    private static void shellSort(int[] arr) {
        //临时存放
        int temp;
        for (int gap = arr.length; gap > 0; gap /= 2) {
            //分组的次数
            for (int i = gap; i < arr.length; i++) {
                //插入的位置
                int insertIndex = i;
                //要插入的值
                int insertValue = arr[insertIndex];
                while (insertIndex - gap >= 0 && arr[insertIndex] < arr[insertIndex - gap]) {
                    arr[insertIndex] = arr[insertIndex - gap];
                    insertIndex -= gap;
                }
                arr[insertIndex] = insertValue;
            }
        }
    }
}
